#include "junix.h"

template <typename Type>
void insertion(Type v[],int size) 
{
	for (int i=1;i<size;i++) 
	{
		Type t=v[i];
		int j=i-1;
		for (;j>=0;j--) 
		{
			if (v[j]>t) 
			{
				v[j+1]=v[j];
				if (j==0) 
					v[j]=t;
			} else {
				v[j+1]=t;
				break;
			}
		}
	}
}

template <
typename Type,
typename Compare
>
void insertion(Type v[],int size,Compare comp)
{
	for (int i=1;i<size;i++)
   	{
		Type t=v[i];
		int j=i-1;
		for (;j>=0;j--)
	   	{
			if (comp(t,v[j])) 
			{
				v[j+1]=v[j];
				if (j==0) 
					v[j]=t;
			} else {
				v[j+1]=t;
				break;
			}
		}
	}
}

int main(int argc, char **argv)
{
	const int sz = 1000000;
	std::vector<int> v(sz);
	std::generate(v.begin(),v.end(),
			boost::bind(std::modulus<int>(), boost::bind(rand), sz));
	jtime T;
	T.start();
	insertion(&v[0],v.size());
	T.end();
	T.print();

	//std::copy(v.begin(),v.end(),std::ostream_iterator<int>(std::cout," "));
	//std::cout<<std::endl;
}
